perm filename OCCULT[00,BGB]2 blob
sn#111641 filedate 1974-07-17 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00010 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 {[C <N αOCCULT λ30 P40 I425,0 JC FA} SECTION 4.
C00005 00003
C00009 00004
C00010 00005 [4.1 Hide Marking a Coherent Object.]
C00014 00006 [4.2 Edge-Edge and Face-Vertex Comparing]
C00015 00007 [4.3 Recursive Windowing.]
C00019 00008 [4.4 Propagating Underfaces and Shadows.]
C00020 00009 [4.5 Photometric Modeling and Video Generation.]
C00022 00010 [4.6 Performance of OCCULT and Related Work.]
C00023 ENDMK
C⊗;
{[C; <N; αOCCULT; λ30; P40; I425,0; JC; FA} SECTION 4.
{JC; FD} HIDDEN LINE ELIMINATION FOR COMPUTER VISION.
{λ7; W250; JA; FA}
4.0 Introduction to Hidden Line Elimination.
4.1 Hide Marking a Coherent Object.
4.2 Edge-Edge and Face-Vertex Comparing
4.3 Recursive Windowing.
4.4 Propagating Underfaces and Shadows.
4.5 Photometric Modeling and Video Generation.
4.6 Performance of OCCULT and Related Work.
4.7 Summary of OCCULT Techniques.
{λ30;W0;I950,0;JUFA}
[4.0 Introduction to Hidden Line Elimination.]
Hidden line elimination refers to the process of simulating
the appearance of opaque three dimensional objects. The phrase
<hidden line elimination> dates from when the problem only involved
deleting the undesired, that is the <hidden> lines, from a line
drawing; today the phrase persists but connotes the wider problem of
synthesizing realistic images using a computer. The present
discussion is about techniques which have been implemented in a
particular hidden line eliminator named OCCULT. The name <OCCULT>
literally means <to hide>. Employing the GEOMED routines and the
winged edged polyhedron representation, OCCULT illustrates novel
solutions to the graphics problems of exploiting object coherence and
frame coherence, of combining image space and model space
techniques, and of spatial sorting of faces, edges and vertices in
two dimensions.
OCCULT is further distingushed by its intended application to
computer vision and robotics. Whereas in computer graphics the
results of hidden line elimination are intended for human viewing, in
computer vision the output is intended for further machine
processing. In vision, the output of a hidden line eliminator must
be in a form appropriate for some kind of automatic image comparing
process. In particular, the prime design goal for OCCULT was to
output a coherent graph of regions, edges and vertices that covered
the image rectangle plane with no holes missing, no regions
overlapping and no dangling edges. It was naively assumed that such a
highly structured image representation, called a <mosaic image>,
would provide a suitable basis for deriving data such as the location
and orientation of high contrast edges without having to generate
video image.
The idea of using a hidden line eliminator in a vision system
is not new and has appeared in two other vision systems, one by
Larry Roberts (ref **) and one by Gill Falk (ref **); the present
system is a direct heir of the work of both Roberts and Falk in that
the last version of the Falk system contained one of the early
versions of OCCULT (as installed by Richard Orban).
Finally, I reject the view that the hidden line elimination
problem has been adequately solved. Like image anaylsis, image
synthesis which is hidden line elimination, is going to continue to
be a perenial research problem because it can not be isolated from
physical modeling. Metaphorically, hidden line elimination is the
visible tip of the iceberg of physical simulation, weaknesses of the
underlying model literally shows up in passing through the process of
image synthesis. The present day collection of techniques are still
quite lacking in realism, economy, flexibility and even reliability.
Initialization for Hidden Line Elimination.
---------------------------------------------------------------------
Perspective Projection
FMark
Face Z-clipping
Potent & Visible Bits
Face Coefficients
EMark
Edge Coefficients
Folded Edges.
[4.1 Hide Marking a Coherent Object.]
OCCULT marks the faces, edges and vertices of a polyhedral
scene as being, either visible or hidden with respect to a simulated
camera. Edges that were at first partially visible are split into
pieces so that each piece is either fully visible or fully hidden. In
a modeling environment that provides coherent polyhedra that can be
easily traveled and modified, the simple technique of hide marking
the neighbors of entities already hidden can be used to do almost all
of the actual hiding, once a starting place has been found.
In OCCULT, the two innermost routines, EHIDE and VHIDE,
perform this kind of marking. The routine VHIDE takes two arguments:
the vertex, V, which is to be marked as hidden and the face, F, that
is known to hide V; the routine then simply calls EHIDE for each
potentially visible edge of V's perimeter. EHIDE in turn takes three
arguments: an overface, F, an edge, E, and one vertex, V, of that
edge which is known to be hidden by F. EHIDE then checks to see
whether or not E leaves its overface, F, there are three basic cases:
(i) E does not leave F, so it is marked as hidden and VHIDE is
applied to the vertex OTHER(E,V); (ii) E does leave overface F by
crossing under an edge which provides a new overface for EHIDE to
check; or (iii) E leaves F by crossing under a <folded> edge, so
EHIDE splits the original edge, E, and the folded edge to form a
T-joint marking the hidden portion of E as hidden and leaving the
remaining portion of E potentially visible.
T-joints & Folded Edges.
[4.2 Edge-Edge and Face-Vertex Comparing]
Edge-Edge Comparing
i. Identity case (E1 ≡ E2)
ii. Topologically connected
Test for edges already having a vertex of tjoint in common.
iii. Span Overlap Test
to prevent nasty colinear cases.
iv. Compare for crossing
v. Fudge (Move towards right and down).
Face-Vertex Comparing
Zdepth
Within
Two very simple kinds of hidden line eliminators that almost
work are based on combining edge-edge comparing or face-vertex
comparing with coherent object hidding.
[4.3 Recursive Windowing.]
Recursive windowing is the
will push them into a window and will then sub divide the
window recursively until a desired condition is achieved.
This section describes a two dimensional spatial sorting
technique for partitioning the faces, edges and vertices associated
with a given rectangular region called a window, into two subwindows.
The general idea of the sort technique
stems from the hidden line eliminators of Warnock (ref. **)
and Sutherland (ref. **); however ESORT is unique in that it
maintains a data structure which allows edges to be split during the
sort and its makes fewer compares than any of its predessors.
Window Structure.
The sort window itself is a twelve word node which contains
data fields named XLO, XHI, YLO and YHI which specify the boundary of
the window and data fields named PENCNT, SURCNT, EDGCNT and VCNT
which specify the number of faces that penetrate or surround the
window, the number of edges that pass through the window and the
number of vertices that fall within the window. The window contains
sufficient link fields to hold pointers to the head of the pen-face
list, the sur-face list, the vertex list, the head and tail of its
edge list and a pointer to its antecedent window.
Bead Structure.
A bead is a two word node that contains four pointers and
which represents one instance of an edge passing through a window.
Each edge has a list of beads representing an ordered list of the
window through which it (the edge) passes; and each window has a list
of beads representing a list of the edges it contains. The link
fields named WND and EDG of a bead, point to the particular window
and the particular edge to which the bead belongs. The link fields
named WNBL and EDBL of a bead contain the necessary links for the
window's bead list and for the edge's bead list.
Routines:
i. Make Sort Window.
ii. Push Sort Window.
iii. Pop Sort Window.
iv. Bead List Edit.
[4.4 Propagating Underfaces and Shadows.]
[4.5 Photometric Modeling and Video Generation.]
The light scattering properties of ordinary surfaces can be
modeled by thinking of the surface as composed of many little
mirrors. The orientation of each mirror is described by two angles,
its tilt from the normal vector of the surface and its pan about the
normal vector with respect to a specified reference vector in the
tangent plane of the surface. For a perfect reflecting surface all
the differential mirrors have a zero pan and tilt; for isotropic
conventional surfaces the statistical distribution of pan
orientations is flat and the distribution of tilt orientations is a
blip function; and for a perfect isotropic Lambert surfaces both the
pan and tilt distributions are flat.
[4.6 Performance of OCCULT and Related Work.]
[4.7 Summary of OCCULT Techniques.]